package cg.studio.algorithm.tree;

import java.util.Stack;

public class TreeStackTraverse extends TreeAbstractTraverse
{
  // traverse the tree by keeping the super node on the stack
  // no support post traverse
  public < T > void deepthTraverse( BinaryTree< T > root, DeepthTraverseOrder traverseOrder )
  {
    Stack<BinaryTree<T>> stack = new Stack<BinaryTree<T>>();
    
    while( true )
    {
      //traverse left
      while( root != null )
      {
        if( DeepthTraverseOrder.PreOrder == traverseOrder )
          root.display();

        //should push it even if left is null, as right maybe not null
        stack.push( root );
        root = root.getLeft();        
      }
      
      //get root from stack
      if( stack.isEmpty() )
        return;
      root = stack.pop();
      if( DeepthTraverseOrder.InOrder == traverseOrder )
        root.display();
      
      //traverse right branch
      root = root.getRight();
    }
  }

}
